perm filename GEM[0,BGB]4 blob
sn#081308 filedate 1974-01-11 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00012 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 3.0 Geometric Modeling Theory.
C00004 00003 3.1 Modeling Design Goals.
C00008 00004 3.X Light Scattering Model
C00010 00005 3.2 Kinds of Geometric Models.
C00012 00006 3.X Camera Model.
C00025 00007 3.X Polyhedron Modeling.
C00027 00008 3.X The Vertex.
C00031 00009 3.X The Edge.
C00034 00010 3.X The Face.
C00037 00011 3.X Three kinds of perimeters.
C00043 00012 3.X Accessing.
C00047 ENDMK
C⊗;
3.0 Geometric Modeling Theory.
3.0 Introduction.
Geometric modeling literally means representing the
measurement of the earth. In the specific context of computer
graphics, geometric modeling refers to constructing computer
representations of physical objects, cameras, images and light for
the sake of numerically simulating their behavior in space and time.
Ignoring subtleties, geometric world modeling is distinguished from
semantic and logical modeling in that it is quantitative and
numerical rather than qualitative and symbolic. Practical modeling
issues involve which aspects of the world are significant; which
programming technologies should be used; and what are the trade offs
between storing the model and recomputing the model.
3.1 Modeling Design Goals.
The main requirement of a geometric model for computer vision
is that it be able to represent the visual appearance of the
mundane physical world.
The visual appearance of the world on a human scale,
indeed our very notion of concrete reality,
is dominated by objects that are solid and opaque.
Geometrically, a solid opaque object can be
enveloped by a continuous unbroken non-intersecting
two dimensional surface, such surfaces or manifolds
have an unabiguous inside and an outside.
Solid objects can be moved about in space however
two solid objects can not occupy the same space at the same time.
1. Representation of manifolds.
2. Detection and Prevention of Manifold Intersection.
3. Manifold Photometric models.
inertia, continuity,
collision, friction, gravity,
Translucent and
water, cloth, glass and smog
geometric, topological, photometric and structural data
3.X Light Scattering Model
The light scattering properties of ordinary surfaces can be
modeled by thinking of the surface as composed of zillions of little
differential mirrors.
The orientation of each mirror is described by
two angles, its tilt from the normal vector of the surface and its
pan about the normal vector with respect to a specified reference
vector in the tangent plane of the surface. For a fully mirror like
surface all the differential mirrors have a zero pan and tilt; for
isotropic conventional surfaces the the statistical distribution of
pan orientations is flat and the distribution of tilt orientations is
a blip function; and for perfect isotropic Lambert surfaces both the
pan and tilt distributions are flat.
3.2 Kinds of Geometric Models.
---------------------------------------------------------
| Five kinds of geometric models: |
| |
| 1. 3-D Space Array. |
| 2. 2-D Surface Function Z=F(x,y). |
| 3. Manifolds. |
| 4. Polyhedral: Body, Face, Edge, Vertex. |
| 5. Skeltal models. |
| 6. Cross Section. |
| 7. Cellular. |
---------------------------------------------------------
3.X Camera Model.
The particular camera model I have been using, is
expressed by eighteen real numbers involving nine degrees of freedom.
First there is the camera lens center locus:
CX, CY, CZ, in world coordinates.
Afixed to the lens center is the camera frame of reference with unit
vectors i, j and k. When the image formed by the camera is placed in
correspondence to a display screen, as illustrated in figure 1.3, the
unit vector i maps into the rightward positive x of the display
screen, and the unit vector j maps into the upward positive y of the
display screen, and the unit vector k comes out of the display screen
to form a right handed coordinate system. Together the three unit
vectors of the camera are the three by three rotation matrix:
IX, IY, IZ
JX, JY, JZ in world coordinates.
KX, KY, KZ
Next, there are three scales which determine the correspondence
between world size and image size. Observe that the world is measured
in physical units of length like meters or feet while computer images
come in integral sizes like 1024 by 1024 or 480 rows by 512 columns,
thus the conversion scales must be in terms of logical image units
per physical world units. In an actual television camera a minute
image (say 9mm by 12mm) is formed on a vidicon tube and that image
has a particular number of rows and columns. It is the little image
on the vidicon that we pretend to model by the six parameters:
LDX, LDY, LDZ Logical raster size.
PDX, PDY, FOCAL Physical raster size.
Where the number named FOCAL, is the focal plane distance which in
this model (with distant objects) can safely be equated with the lens
focal length and can be given in millimeters (conventional lens run
12.5mm to 75mm for 1" TV). The integer LDZ is an artifact so that
the units come out correctly in the Z dimension. Thus the scales
factors are defined:
SCALEX ← -FOCAL*LDX/PDX;
SCALEY ← -FOCAL*LDY/PDY;
SCALEZ ← FOCAL*LDZ;
This simple camera model is used to compute vertex image
coordinates.
3.X Polyhedron Modeling.
In elementary geometry, a polyhedron is said to be a solid
formed (or bounded) by plane faces; the word "polyhedron" literally
meaning "many-faced". Topologically, simple polyhedra satisfy
Euler's F-E+V=2 equation; where F, E and V are the number of faces,
edges and vertices of the polyhedron respectively. This equation was
known to Descartes in 1640, but the first proof wasn't given until
1752, when Euler proved the relation by considering the graph
corresponding to the edges of polyhedra. A simple polyhedron is one
homeomorphic to a sphere.
SOLID POLYHEDRON
1. Satisfies Eulers Equation F-E+V=2*B-2*H
2. All vertives and faces have three or more edges.
3. No two vertices are coincidant.
4. No edge intersects a face or vertex
to which it doesn't belong.
3.X The Vertex.
A vertex is a labeled point in a Euclidean three
space. The important thing about a vertex is its world locus (with
component names XWC,YWC,ZWC standing for world-coordinates). Vertex
locii are the basic geometric data from which length, area, volume,
face vectors and image positions can be computed.
Also a Vertex may
exist simultaneously in one or more image spaces. An image space
(with component names XPP,YPP,ZPP standing for perspective-projected)
is always three dimensional and is determined with respect to a given
camera centered coordinate system (with component names XCC,YCC,ZCC
standing for camera-coordinates). The third image component, ZPP,
is taken inversely proportional to the distance of the vertex from
the camera image plane, ZCC. Using the camera of the previous
section. The transformation of a vertex world locus to a camera
centered locus is:
X ← XWC - CX;
Y ← YWC - CY;
Z ← ZWC - CZ;
XCC ← IX*X + IY*Y + IZ*Z;
YCC ← JX*X + JY*Y + JZ*Z;
ZCC ← KX*X + KY*Y + KZ*Z;
The first three assignment statements are the translation to
the camera frame's origin, the second three assignments are the
rotation to the camera frame's orientation. Next the perspective
projection transformation is computed:
XPP ← SCALEX*XCC/ZCC;
YPP ← SCALEY*YCC/ZCC;
ZPP ← SCALEZ /ZCC;
The XPP and YPP assignments are derived by means of similar
triangles, as is being done by the man in figure 1.5; the Zpp
assignment is for preserving the depth information and the
colinearity of the world in the perspective projected image space. As
given, the PP frame is right handed and vertices in front of the
camera's image plane will have negative Zpp; Zpp values near -FOCAL
are close to the camera and values approaching zero are far away.
A final matter with respect to vertices is their valence. The
valence of a vertex is the number of edges that meet at the vertex. A
vertex valence of three, for example, indicates a trihedral corner.
3.X The Edge.
For a start, the structure of an edge need be thought of as
little more than two vertices; the topological subtlety of edges will
be explained later. However, two vertices do define the important
geometric edge data called the line coefficients. Named AA, BB,
CC; these coefficients are computed from the perspective locus of the
edge's endpoints as follows:
AA ← Y1 - Y2;
BB ← X2 - X1;
CC ← X1*Y2 - X2*Y1;
These coefficients appear in the 2D equation of the line that
contains the edge:
0 = AA*X + BB*Y + CC;
When the edge coefficients are normalized:
L ← SQRT(AA↑2+BB↑2);
AA ← AA/L;
BB ← BB/L;
CC ← CC/L;
the line equation gives the distance, of a point X,Y from the line:
Q ← AA*X + BB*Y + CC;
The distance is actually ABS(Q), since Q is negative on one side side
of the line; also if one were standing on the plane at point X1,Y1
facing X2,Y2 the Q positive half-plane would be on your left and the
Q negative half plane would be on your right.
An important operation on two edges is to detect whether or
not they intersect; this can be decided by checking first whether the
endpoints of one edge are in the opposite half planes of the other
edge, and second whether the endpoints of the latter edge are in the
opposite half planes of the first. When both conditions obtain, then
the intersection point can be found:
T ← (A1*B2 - A2*B1);
X ← (B1*C2 - B2*C1)/T;
Y ← (A2*C1 - A1*C2)/T;
An actual compare for intersection should initially check for the
identity case, and for edges with a vertex in common.
3.X The Face.
A face is a finite region of plane enclosed by straight
lines. A safe formal face structure could be built by defining a
triangle as three non-colinear vertices and then insisting that all
faces be triangle interiors. Unhappily, BFEV faces are usually
represented as a list of vertices and edges (or by something nearly
equivalent) for the sake of saving memory space. Such `list' faces
are not monolithic but tend to suffer special cases and pathologies
such as:
Coincident or crossing edges,
Holes and Disjointness,
Concavity (& Convexity),
Non-coplanarity.
Like edges, faces have characteristic coefficients. Face coefficients
satisfy the equation of a plane in which the face is embedded:
AA*X + BB*Y + CC*ZZ = KK.
The equation could be divided by KK, but that is undesirable because
the AA, BB, CC are more useful as a unit normal vector, in which case
KK is the distance of the origin from the plane. Given the locii of
three non-colinear vertices, the coefficients of a plane can be
computed by Kramer's rule as follows:
KK ← X1*(Z2*Y3-Y2*Z3)
+ Y1*(X2*Z3-Z2*X3)
+ Z1*(Y2*X3-X2*Y3);
AA ← (Z1*(Y2-Y3) + Z2*(Y3-Y1) + Z3*(Y1-Y2));
BB ← (X1*(Z2-Z3) + X2*(Z3-Z1) + X3*(Z1-Z2));
CC ← (X1*(Y3-Y2) + X2*(Y1-Y3) + X3*(Y2-Y1));
and normalized:
ABC ← SQRT(AA↑2 + BB↑2 + CC↑2);
AA ← AA/ABC;
BB ← BB/ABC;
CC ← CC/ABC;
KK ← KK/ABC;
If the given vertices V1, V2, V3 had been taken going counter
clockwise about the face as viewed from the exterior of the solid,
then the following relations obtain:
AA*X + BB*Y + CC*Z > KK implies X,Y,Z above the plane.
AA*X + BB*Y + CC*Z = KK implies X,Y,Z in the plane.
AA*X + BB*Y + CC*Z < KK implies X,Y,Z below the plane.
Face coefficients prove useful in both world and image coordinates.
3.X Three kinds of perimeters.
FACE PERIMETER - a face is surrounded by edges and vertices.
VERTEX
⊗
/ \
/ \
/ \
/ \
EDGE / \ EDGE
/ \
/ FACE \
/ \
/ \
/ \
VERTEX ⊗---------------------⊗ VERTEX
EDGE
VERTEX PERIMETER - a vertex is surrounded by edges and faces.
EDGE
|
|
FACE | FACE
|
⊗ VERTEX
/ \
/ \
/ \
/ \
/ FACE \
EDGE EDGE
EDGE PERIMETER - an edge is surrounded by 2 faces & 2 vertices.
VERTEX
⊗
|
|
FACE E FACE
|
|
⊗
VERTEX
3.X Accessing.
A BFEV model has four kinds of accessing. The most
conventional BFEV access is retrieval by symbolic name which requires
a symbol table. Next, between bodies there is Parts-Tree accessing.
At the top of the Parts-Tree is a special body named the world to
which all the other bodies are attached; thus the world body serves
as an OBLIST node. Given a particular body, a list of its sub-parts
can be retrieved as well as its supra-part or "supart". A supart is
the whole entity to which a part belongs, the world being its own
supart.
Within each body there is face, edge and vertex sequential
accessing. Given a body, all its faces, or edges, or vertices need to
be readily available since perspective projection loops thru all the
vertices, and the process of display clipping loops thru all the
edges, and the act of checking for body intersection loops thru all
the faces.
Finally, among the faces, edges and vertices of a body there
is perimeter accessing. Faces have a perimeter of edges and vertices
[figure 1.6]; less commonly used, vertices have a perimeter of edges
and faces [figure 1.7]; and of particular note, edges have a
perimeter always formed by two faces and two vertices, [figure 1.8].
Perimeter accessing requires that given a face, edge or vertex, that
the perimeter of that entity be readily accessible. Since the surface
of a polyhedron is orientable, that is has a well defined inside and
outside, (Klein bottles with their crosscaps will not be modeled),
such perimeter lists can be ordered (say clockwise) with respect to
the exterior of the polyhedron. Perimeter accessing is mentioned in
Guzman and Falk and is the underlying
basis of part-II of this paper which presents a polyhedron model
built for accessing and altering face, edge and vertex perimeters.